package com.tensai.study.基础.算法.压缩.哈夫曼;

import com.tensai.study.基础.数据结构.树.二叉树.BinaryTree;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 哈夫曼压缩的意义在于
 * 编码是变长的，是根据加权最优树来的，根据使用次数的多少权重高的编码越短
 */
public class Test {

    private static final String s = "MySQL 8.0 Reference Manual\n" +
            "Including MySQL NDB Cluster 8.0\n" +
            "Abstract\n" +
            "\n" +
            "This is the MySQL™ Reference Manual. It documents MySQL 8.0 through 8.0.22, as well as NDB Cluster releases based on version 8.0 of NDB through 8.0.20-ndb-8.0.20, respectively. It may include documentation of features of MySQL versions that have not yet been released. For information about which versions have been released, see the MySQL 8.0 Release Notes.\n" +
            "\n" +
            "MySQL 8.0 features.  This manual describes features that are not included in every edition of MySQL 8.0; such features may not be included in the edition of MySQL 8.0 licensed to you. If you have any questions about the features included in your edition of MySQL 8.0, refer to your MySQL 8.0 license agreement or contact your Oracle sales representative.\n" +
            "\n" +
            "For notes detailing the changes in each release, see the MySQL 8.0 Release Notes.\n" +
            "\n" +
            "For legal information, including licensing information, see the Preface and Legal Notices.\n" +
            "\n" +
            "For help with using MySQL, please visit the MySQL Forums, where you can discuss your issues with other MySQL users.\n" +
            "\n" +
            "Document generated on: 2020-05-01 (revision: 65876)";

    public static void main(String[] args) {
        List<String> list = Arrays.asList(s.split(""));
        Map<String, List<String>> map = list.stream().collect(Collectors.groupingBy(String::toString));
        List<BinaryTree> binaryTreeList = new ArrayList<>();
        map.forEach((k, v) -> {
            BinaryTree binaryTree = new BinaryTree(k, v.size());
            binaryTreeList.add(binaryTree);
        });
        treeBuilder(binaryTreeList);
        Map<String, String> codeMap = new HashMap<>(4);
        huffCode(binaryTreeList.get(0), "", codeMap);
        codeMap.forEach((k, v) -> System.out.println(k + "\t" + v));
        //TODO 字典替换，八位分割转ASCII或者32位转int（其实都是二进制转换）无所谓的

        //FIXME
    }

    /**
     * 森林变哈夫曼树
     *
     * @param binaryTreeList 哈夫曼森林
     */
    public static void treeBuilder(List<BinaryTree> binaryTreeList) {
        if (binaryTreeList.size() == 1) {
            return;
        }
        binaryTreeList.sort(Comparator.comparingInt(BinaryTree::getWeight));
        BinaryTree binaryTree = new BinaryTree(binaryTreeList.get(0), binaryTreeList.get(1));
        //删除前两个元素，不用奇怪，删掉第0个之后，第1个会变成第0个
        binaryTreeList.remove(0);
        binaryTreeList.remove(0);
        binaryTreeList.add(binaryTree);
        treeBuilder(binaryTreeList);
    }

    /**
     * 遍历哈夫曼树，构造哈夫曼编码字典
     *
     * @param binaryTree 哈夫曼树
     * @param codeFlag   游标位置
     * @param codeMap    哈夫曼字典
     */
    public static void huffCode(BinaryTree binaryTree, String codeFlag, Map<String, String> codeMap) {
        if (binaryTree.getLeft() == null) {
            codeMap.put(binaryTree.getValue(), codeFlag + binaryTree.getCode());
        } else {
            codeFlag += binaryTree.getCode();
            huffCode(binaryTree.getLeft(), codeFlag, codeMap);
            huffCode(binaryTree.getRight(), codeFlag, codeMap);
        }
    }
}
